11026. Задача группирования

Имеется n чисел. Выберем из них группу из k элементов. Две группы считаются разными, если существует хотя бы один элемент, который принадлежит одной группе и не принадлежит другой. Группирующей системой будем называть множество всех возможных групп. Например, из четырех элементов a, b, c, d можно составить шесть групп по два элемента. Группирующей системой для множества {a, b, c, d} и k = 2 будет множество {ab, ac, ad, bc, bd, cd}.

Похожестью группирующей системы называется число, равное сумме произведений всех элементов групп, взятой по модулю m. Похожесть для представленного выше примера для k = 1 равна F₁ = (a + b + c + d) mod m. Для k = 2 похожесть равна F₂ = (ab + ac + ad + bc + bd + cd) mod m.

Для заданного множества чисел и среди всех всевозможных k = 1, …, n найти похожесть F_k с максимальным значением.

Вход. Первая строка каждого теста содержит числа n (2 £ n £ 1000) и m (1 £ m £ 2³¹). Следующая строка содержит n положительных целых чисел. Все числа не более 1000. Последний тест содержит n = m = 0 и не обрабатывается.

Выход. Для каждого теста вывести значение максимальной похожести среди всех возможных групп.

Пример входа

4 10

1 2 3 4

4 100

1 2 3 4

4 6

1 2 3 4

0 0

Пример выхода

5

50

5

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть а₁, a₂, …, a_n – заданные n чисел. Обозначим через F_ik (i ³ k) сумму всех возможных произведений по k чисел, взятых среди первых i чисел a₁, …, a_i. Построим следующую таблицу F_ik:

i \ k	1	2	3
1	a1
2	a1 + a2	a1a2
3	a1 + a2 + a3	a1a2 + a1a3 + a2a3	a1a2a3

Имеют место следующие рекуррентные соотношения:

F_i1 = F_(i-1)1 + a_i, F_ii = F_{(i-1) (i-1)} * a_i, 1 £ i £ n

F_ik = F_(i-1)k + F_{(i-1) (k-1)} * a_i, 1 £ i £ n, 1 < k < i

Значения каждой следующей строки пересчитываются через значения предыдущей строки, поэтому в памяти достаточно хранить один линейный массив d размера 1000. При этом пересчет значений i - ой строки следует начинать с конца: сначала вычислить F_ii, потом F_i(i-1) и так далее до F_i1. Все вычисления следует проводить по модулю m.

Пример

Рассмотрим первый тест. Построим две таблицы: вычисления во второй будут производиться по модулю m = 10, а в первой – нет.

i \ k	1	2	3	4	i \ k	1	2	3	4
1	1				1	1
2	3	2			2	3	2
3	6	11	6		3	6	1	6
4	10	35	50	24	4	0	5	0	4

Ответом является максимальное число в четвертой строке второй таблицы.

Реализация алгоритма

Объявим линейный массив d, в котором будут пересчитываться значения F_ik.

long long d[1000];

Вводим количество чисел n и значение m. Для каждого входного теста изначально обнуляем массив d. Первое число a₁ заносим в d[0].

while(scanf("%lld %lld",&n,&m), n + m > 0)

{

memset(d,0,sizeof(d));

scanf("%lld",&d[0]);

Вводим значение num = a_i+1 (1 £ i < n) и пересчитываем значения F_ik, k = i, i – 1, …, 1 по выше приведенным рекуррентным формулам. Все вычисления проводим по модулю m.

for(i = 1; i < n; i++)

{

scanf("%lld",&num);

d[i] = (d[i-1] * num) % m;

for(j = i - 1; j > 0; j--)

d[j] = (d[j-1] * num + d[j]) % m;

d[0] = (d[0] + num) % m;

}

Находим максимальное значение среди элементов массива d и заносим его в переменную res. Выводим результат.

res = d[0];

for(i = 1; i < n; i++)

if (d[i] > res) res = d[i];

printf("%lld\n",res);

}